/*
 * @lc app=leetcode.cn id=72 lang=javascript
 *
 * [72] 编辑距离
 */

// @lc code=start
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  let m = word1.length;
  let n = word2.length;
  //dp[i][j]表示word1[0,i]和word2[0,j]最小编辑距离
  const dp = new Array(m + 1).fill(0).map((_) => new Array(n + 1).fill(0));
  // 明确base case
  for (let i = 1; i <= m; i++) {
    // j为0，表示需要删除的操作步骤
    dp[i][0] = i;
  }
  for (let j = 1; j <= n; j++) {
    // i为0，表示需要插入的操作步骤
    dp[0][j] = j;
  }

  // 0是base case 状态，需要从1开始遍历，所以word1和word2的访问需要-1
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
      }
    }
  }
  return dp[m][n];
};
// @lc code=end
